package n1458;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int LCS(String a, String b) {
		int f[][] = new int[2][b.length() + 1];

		for (int i = 0; i < b.length() + 1; i++) {
			f[0][i] = 0;
		}
		for (int i = 0; i < 2; i++) {
			f[i][0] = 0;
		}

		for (int i = 0; i < a.length(); i++) {
			for (int j = 0; j < b.length(); j++) {
				if (a.charAt(i) == b.charAt(j)) {
					f[1][j + 1] = f[0][j] + 1;
				} else {
					f[1][j + 1] = Math.max(f[0][j + 1], f[1][j]);
				}
			}
//			压缩存储
			for(int k=0;k<b.length()+1;k++)
			{
				f[0][k]=f[1][k];
			}
		}
		return f[1][b.length()];

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String line=null;
		while((line=bf.readLine())!=null)
		{
			StringTokenizer st=new StringTokenizer(line);
			String a=st.nextToken();
			String b=st.nextToken();
			System.out.println(LCS(a,b));
		}
	}

}
